#ifndef _SLL_
#define _SLL_


template <typename Type = int> class SLLIter;

template <typename Type>
class SLList
{
	friend class SLLIter<Type>;

	struct node
	{
		Type data;
		node* next;
	};

	node* head;

public:

	///////////////////////////////////////////////////////////////////////////////
	// Function : Constructor
	// Notes : constructs an empty list
	///////////////////////////////////////////////////////////////////////////////
	SLList() { head =  0; }

	///////////////////////////////////////////////////////////////////////////////
	// Function : Destructor
	// Notes : Destroys the list
	///////////////////////////////////////////////////////////////////////////////
	~SLList()
	{
		clear();

	}
	///////////////////////////////////////////////////////////////////////////////
	// Function : Assignment Operator
	///////////////////////////////////////////////////////////////////////////////
	SLList<Type>& operator=(const SLList<Type>& that)
	{

		if(this != &that )
		{
			clear();

			if(that.head)
			{

				node* i = that.head;


				node* temp =  new node;
				temp->data = i->data;

				temp->next = 0;
				head = temp;
				i = i->next;

				node* j = head;
				while(i)
				{
					temp = new node;
					temp->data = i->data;

					temp->next = 0;
					j->next = temp;
					i = i->next;
					j = j->next;
				}

			}
		}

		return *this;
	}
	///////////////////////////////////////////////////////////////////////////////
	// Function : Copy Constructor
	///////////////////////////////////////////////////////////////////////////////
	SLList(const SLList<Type>& that)
	{
		head = 0;

		if(that.head)
		{

			node* i = that.head;


			node* temp =  new node;
			temp->data = i->data;

			temp->next = 0;
			head = temp;
			i = i->next;

			node* j = head;
			while(i)
			{
				temp = new node;
				temp->data = i->data;

				temp->next = 0;
				j->next = temp;
				i = i->next;
				j = j->next;
			}

		}


	}
	///////////////////////////////////////////////////////////////////////////////
	// Function : addHead
	// Parameters :	v - the item to add to the list
	///////////////////////////////////////////////////////////////////////////////
	void addHead(const Type& v)
	{

		node* tmp = new node;

		tmp->data = v;
		tmp->next = head;
		head = tmp;



	}
	///////////////////////////////////////////////////////////////////////////////
	// Function : clear
	// Notes : clears the list, freeing any dynamic memory
	///////////////////////////////////////////////////////////////////////////////
	void clear()
	{

		while(head)
		{
			node* tmp;

			tmp = head;
			head = head->next;

			delete tmp;

		}
	}
	///////////////////////////////////////////////////////////////////////////////
	// Function : insert
	// Parameters :	index - an iterator to the location to insert at
	//				v - the item to insert
	// Notes : do nothing on a bad iterator
	///////////////////////////////////////////////////////////////////////////////
	void insert(SLLIter<Type>& index, const Type& v)
	{
		if(index.curr != head)
		{
			node* tmp = new node;

			tmp->data = v;

			tmp ->next = index.curr;
			index.prev->next = tmp;
			index.curr = tmp;
		}else if(head)
		{
			node* tmp = new node;

			tmp->data = v;
			tmp->next = head;
			head = tmp;

			index.curr = tmp;
		}


	}

	///////////////////////////////////////////////////////////////////////////////
	// Function : remove
	// Parameters :	index - an iterator to the location to remove from
	// Notes : do nothing on a bad iterator
	///////////////////////////////////////////////////////////////////////////////
	void remove(SLLIter<Type>& index)
	{
		if(index.curr != head)
		{
			if(index.prev && index.curr)
			{
				node* tmp = index.curr;

				index.curr = index.curr->next;
				index.prev->next = index.curr;

				delete tmp;

			}

		}else if(head)
		{
			node* tmp;

			tmp = head;
			head = head->next;


			delete tmp;

			index.curr = head;
		}

	}

	bool IsEmpty() { return head == 0;}

};

template <typename Type>
class SLLIter
{
	friend class SLList<Type>;

	typename SLList<Type>::node * curr;
	typename SLList<Type>::node * prev;
	SLList<Type>* list;



public:
	///////////////////////////////////////////////////////////////////////////////
	// Function : Constructor
	// Parameters :	listToIterate - the list to iterate
	///////////////////////////////////////////////////////////////////////////////
	SLLIter(SLList<Type>& listToIterate) 
	{
		list = &listToIterate;

	}
	///////////////////////////////////////////////////////////////////////////////
	// Function : begin
	// Notes : moves the iterator to the head of the list
	///////////////////////////////////////////////////////////////////////////////
	void begin()
	{
		curr = list->head;
		prev = 0;


	}
	///////////////////////////////////////////////////////////////////////////////
	// Function : end
	// Notes : returns true if we are at the end of the list, false otherwise
	///////////////////////////////////////////////////////////////////////////////
	bool end() const
	{
		return !curr;
	}
	///////////////////////////////////////////////////////////////////////////////
	// Function : operator++
	// Notes : move the iterator forward one node
	///////////////////////////////////////////////////////////////////////////////
	SLLIter<Type>& operator++()
	{
		if(curr)
		{
			prev = curr;
			curr = curr->next;
		}

		return *this;

	}
	///////////////////////////////////////////////////////////////////////////////
	// Function : current
	// Notes : returns the item at the current iterator location
	///////////////////////////////////////////////////////////////////////////////
	Type& current() const
	{
		return curr->data;

	}


};


#endif